Turnbull China Bikeride/Turnbull China Bikeride - Disc 1.iso/ARGONET/PD/GAMES/WIMPGAME/MINES2.ZIP/!Mines/Doku

Text File | 1995-02-03 | 9KB | 203 lines

Hallo Michael,

ich habe mit erlaubt, Deinen Code etwas zu ergänzen: es hat mich zu
sehr geärgert, daß man immer nur einen Hint bekommt, obwohl man doch
mehrere brauchte. Und da kam ich auf die Idee eine Routine zu
schreiben, die erst mal prüft, ob der Spieler überhaupt einen Hint
braucht, ihm das mitteilt und ggf. auch gewährt. Um den Zufall gänzlich
auszuschalten, kann der Spieler dann selbst bestimmen, welches Feld
er identifiziert haben möchte. Ich habe diesen Text in folgende Teile
gegliedert: Der Algorithmis, Optimieren, das Endspiel und was ich im
Sourcecode alles verändert habe.

Der Algorithmus
---------------

ist im Prinzip ganz primitiv:
- Suche alle Randpunkte
- Erzeuge alle Belegungen ( für alle Felder Marke/keine Marke )
  das sind 2^anz Stück
- überprüfe alle Belegungen, ob sie keinem aufgedeckten Feld widersprechen,
  d.h. ein Feld mit 3 Nachbarminen 4 oder 2 oder so Marken hat. Wenn
  ja, lösche diese Belegungen
- schaue nach, ob bei allen übrigen Belegungen ein Feld immer eine Mine
  hat oder immer leer ist. Gibt es ein solches Feld, ist diese Belegung
  zwingend und kann durch Schußfolgern gefunden werden.
  Der Spieler braucht dann keinen Tip.

Das habe ich folgendermaßen impementiert ( wenn Du das im Code mitverfolgen
willst, sei gewarnt: durch die Optimierungen sieht alles anders aus, als ich
es hier beschreibe ).

Das Array border_arr enthält die Randfelder. Die maximale Zahl der Randfelder
ist die maximale Zahl der Felder im Spielfeld ( eingendlich ein paar weniger,
denn wenn kein Feld aufgedeckt ist, gibt es auch keine Randfelder ). Also
wird ein entsprechend großer Speicherblock allokiert. border_anz zeigt auf
das Ende des Arrays, d.h. hinter das letzte belegte Element. Das Aufsammeln
der Randfelder geschieht in einer Schleife in init_border durch find_next.

Nachdem die Randfelder alle in diesem Array sind, wird die Rekursions-
routine permutate mit einem Pointer auf das border_arr aufgerufen. Sie
belegt das Feld zuerst nicht, ruft sich selber mit dem Zeiger auf das nächste
Feld auf, setzt dann die Marke und ruft sich ein zweites Mal auf. Ist der
Zeiger gleich border_anz, d.h. am Ende angekommen, wird die Belegung
überprüft, und wenn sie möglich ist ein p_POSSIBLE, sonst ein p_IMPOSSIBLE
zurückgegeben.

Nun muß man nicht tatsächlich alle Belegungen speichern. Es reicht zu wissen,
ob ein Feld immer mit einer Mine belegt war, oder nie, oder ob beides vorkam.
Drei Möglichkeiten kann man in zwei Bits kodieren. Ich habe dazu die Bits 6
und 7 im feld benutzt. Es gibt auch noch einen vierten Initialisierungs-
zustand. Wenn also eine Belegung ohne Marke möglich war, dann wird das mit
einem h_NOMINE vermerkt, es sei denn, das Feld hat schon ein h_MINE oder ein
h_UNKNOWN ( dann gab es schon eine Belegung, bei der dieses Feld eine Marke
hatte, und folglich ist beides möglich ), dann wird es h_UNKNOWN.
Entsprechend, wenn eine Belegung mit eine Marke auf dem Feld möglich ist.

Dieser Algorithmus hat nur ein Problem: die Anzahl der Belegungen, die er
durchprobieren muß, steigt exponentiell mit der Anzahl der Randfelder. Und
da geht auch der schnellste Computer irgendwann ( in der Praxis recht
schnell ) in die Knie. Das Zauberwort heißt oprimieren.

O P T I M I E R E N
-------------------

0. Die trivialen Fälle abprüfen: Ein Fehler bringt natürlich auch meine
so sorgsam optimierten Routinen durcheinander. Deswegen wird der
Spieler erst mal auf einen Fehler hingewiesen, wenn es einen gibt.
Dann das einfache abzählen: Wenn ein Feld genau so viele verdeckte
Nachbarfelder hat wie Minen, muß überall eine Marke drauf; wenn ein
Feld soviele Marken hat wie Minen, müssen alle verdeckten Felder leer
sein. Diese Sachen gehen sehr schnell zu entscheiden und ersparen
Mühsameres.

1. Man kann die Belegungen schon beim Erzeugen auf ihre Gültigkeit
prüfen und entsprechend aussortieren. Das geht folgendermaßen: beim
Erstellen der Liste der Randpunkte wird für alle Nachbarfelder (
die möglicherweise offen sind ) mitgezählt, wieviele Felder in ihrer
Nachbarschaft später in der Liste stehen, d.h. noch verändert werden
können ( das macht find_testmode ). Die Routine test_if_possible zählt
nun für alle offenen Nachbarfelder die benachbarten Marken und Minen.
Wenn es mehr Marken als Minen gibt ist sowiso Ende. Wenn aber die
Summe der Marken und der noch veränderbaren Felder kleiner ist als die
Anzahl der Minen, ist auch Ende, weil, selbst wenn alle folgenden
Felder mit Marken belegt werden, immer zuwenig Marken da sind.

Diese Vorgehensweise hat noch einen zweiten Vorteil: Wenn alle Felder
der Liste belegt wurden, und nicht schon vorher nach obiger Methode
abgebrochen wurde, ist die Belegung auch gültig, d.h. man muß die
Gültigkeit nicht mehr explizit nachprüfen ( ein formaler Beweis steht
noch aus ... ).

2. Es gibt unabhängige Bereiche ( domains ), die getrennt bearbeitet
werden können. Beispiel:

-------------------------
|   |   |   |   |   |   |
-------------------------
|   |R1 | * | * | * |R2 |
-------------------------
|   |R3 | 3 | 3 | 2 |R4 |
-------------------------
|   |R5 | 1 |   |   |   |
-------------------------

Die Wahl von R1,3,5 beeinfußt R2,4 nicht. Und warum ? Weil sie kein
gemeinsames, offenes Nachbarfeld haben. Nach diesem Kriterium kann man
die Liste der Randfelder dann in mehrere Bereiche sortieren ( meistens
). Das wird von der Routine find_domains erledigt. Der Gewinn ist
mitunter enorm: statt bei 20 Feldern 2^20=1048576 Kombinationen durch-
zuackern, sind vielleicht nur 2*10 Felder 2*2^10=2048 Kombinationen zu
berechnen !
Aber Achtung ! Es schleicht sich auch ein Fehler ein: es gibt nur eine
Begrenzte Zahl an Marken, die man noch vergeben kann. Und besonders im
Endspiel gelingt es dadurch, Belegungen auszuschließen und
Schlußfolgerungen zu machen. Dieser Themenkomplex wird ausführlich im
Abschnitt "Das Endspiel" erörtert.

3. Ab und zu kommt es vor, daß zu mehreren, ähnlichen Situationen eine
Hilfe verlangt wird. Und vielleicht hat sich ein Bereich vom letzten
Mal überhaupt nicht verändert und braucht auch nicht nochmal
bearbeitet zu werden. Dazu ist es nötig, die Bereiche zu speichern und
beim nächsten Mal mit den neu erzeugten zu vergleichen. Finden sich
gleiche Bereiche, kann auf die bereits berechneten Ergebnisse
zurückgeriffen werden.

4. Diese Optimierung ist keine algorithmische, aber kein Freak würde
sie unversucht lassen: die Umsetzung der zeitkritischen Routinen in
Assembler, so geschehen mit test_if_possible. Geschwindigkeitsgewinn:
Faktor 2.33.

Das Endspiel
------------

beginnt dann, wenn durch die kleine Zahl der zur Verfügung stehenden
Marken die möglichen Belegungen eingeschränkt werden. Und wie stellt
man das fest ? Ganz einfach: Für jeden Bereich wird ermittelt,
wieviele Marken er mindestens und höchstens braucht. Ist die Summe der
Höchstwerte aller Bereiche größer als die Anzahl der Marken, haben
sich unmögliche Belegungen eingeschlichen. Was tun ?

Die einzige sichere Methode ist, die Sache mit den Bereichen wieder zu
vergessen und alles wie einen einzigen Bereich zu behandeln. Die
Prüfung der Belegung wird um die Begenzung auf die vorhandenen Marken
erweitert.

Es gibt noch etwas, über das man nachdenken muß: Die Felder, die nicht
zum Rand gehören. Es kann nämlich sein, daß sich aus den Minimal- bzw.
Maximal-Werten ergibt, daß alle diese Felder Marken tragen bzw. leer
sind. Es gibt folgende Möglichkeiten:

mines_left - max_mines > rest_felder => Fehler: Es gibt mehr Marken,
als verteilt werden können.

mines_left - max_mines = rest_felder => alle Restfelder haben eine
Marke.

mines_left - min_mines = 0 => alle Restfelder sind leer

Was ich im Source-Code alles verändert habe
-------------------------------------------

1. Die Reihenfolge der Offsets ofs. Das war nicht zwingend nötig, war
aber einfacher für find_testmode.

2. Ich habe das Shaden des Menüeintrags "Hint" verändert: er ist das
ganze Spiel über anwählbar, nur nach dem Ende wird er geshadet.

3. Die Fenster für kein Tip nötig und Feld aufdecken habe ich in das
Template-File aufgenommen und die zugehörigen Handler werden in hint_init
installiert, das in main_init aufgerufen wird.

4. Ich habe ein Fragezeichen-Sprite erfunden, in die Spritedatei
eingefügt und einen Pointer namens questionmark initialisiert ( in
create_sprite )

5. Zur einfacheren Sprite-Ausgabe schrieb ich die Funktion
draw_sprite und habe überall, wo es sinnvoll war, diesen Aufruf
eingesetzt.

6. Um den Aufbau modularer zu machen, habe ich alle globalen #defines,
Datenstrukturen ... in mineheader.h kopiert. Alle öffentlichen
Funktionen von mines.c bzw. hint.c als Prototyp in mines.h bzw. hint.h
eingetragen.

7. Die einfache Win-Funktion habe ich etwas erweitert: Es gibt nun ein
Fenster, das die Anzahl der unötigen Tips anzeigt ( als Motivation,
nicht immer gleich einen Tip zu verlangen ) und zwei Buttons für
neues Spiel und Ende enthält. Das diese Aktionen nun nicht nur vom
Menü-Handler benutzt werden, habe ich sie in eigene Funktionen
gesetzt. Dort wird auch das Win-Fenster wieder geschlossen ( wenn es
überhaupt auf war ).


Und nachdem ich mich nun so sehr reingehängt habe, würde ich mich
glücklich schätzen, wenn Du dieses Programm als neue Version wieder
veröffentlichen würdest und meinen Namen irgendwo vermerktest.


Gunter Blache
Auf dem Wasen 36
71640 Ludwigsburg
[e-mail]